package leetcode;

/*
572. 另一个树的子树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
     3
    / \
   4   5
  / \
 1   2
给定的树 t：
   4
  / \
 1   2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t：
   4
  / \
 1   2
返回 false。
*/

public class problems_572 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(4);
        TreeNode A5 = new TreeNode(5);
        TreeNode A6 = new TreeNode(6);
        TreeNode A7 = new TreeNode(7);
        A1.left = A2;
        A1.right = A3;
        A2.left = A4;
        A2.right = A5;
        A3.left = A6;
        A3.right = A7;
        System.out.println(new Solution().isSubtree(A1, A2));
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if (null == t) return true;
            if (null == s) return false;
            return isSubtree(s.right, t) || isSubtree(s.left, t) || dfs(s, t);
        }

        private boolean dfs(TreeNode node, TreeNode targetNode) {
            if (null == node && null == targetNode) return true;
            if (null == node || null == targetNode) return false;
            if (node.val != targetNode.val) return false;
            return dfs(node.left, targetNode.left) && dfs(node.right, targetNode.right);
        }
    }
}